|
Hall's marriage theorem, or simply Hall's theorem, proved by , is a theorem with two equivalent formulations: * The combinatorial mathematics formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a distinct element from each set. * The graph theoretic formulation deals with a bipartite graph. It gives a necessary and sufficient condition for finding a matching that covers at least one side of the graph. == Combinatorial formulation == Let ''S'' be a family of finite sets, where the family may contain an infinite number of sets and the individual sets may be repeated multiple times.〔. It is also possible to have infinite sets in the family, but the number of sets in the family must then be finite, counted with multiplicity. Only the situation of having an infinite number of sets while allowing infinite sets is not allowed.〕 A ''transversal'' for ''S'' is a set ''T'' and a bijection ''f'' from ''T'' to ''S'' such that for all ''t'' in ''T'', ''t'' is a member of ''f(t)''. An alternative term for ''transversal'' is ''system of distinct representatives''. The collection ''S'' satisfies the marriage condition if and only if for each subcollection , we have : In other words, the number of sets in each subcollection ''W'' is less than or equal to the number of distinct elements in the union over the subcollection ''W''. Hall's theorem states that ''S'' has a transversal if and only if ''S'' satisfies the marriage condition. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hall's marriage theorem」の詳細全文を読む スポンサード リンク
|